package com.zp.self.module.level_4_算法练习.算法.二分查找;

public class 力扣_69_算数评分根{
    public static void main(String[] args) {

        System.out.println(new 力扣_69_算数评分根().mySqrt1(0));
        System.out.println(new 力扣_69_算数评分根().mySqrt1(2));
        System.out.println(new 力扣_69_算数评分根().mySqrt1(4));
        System.out.println(new 力扣_69_算数评分根().mySqrt1(8));
        System.out.println(new 力扣_69_算数评分根().mySqrt1(2147483647));

    }
    /**
     题目：给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

     示例 1：
     输入：x = 4
     输出：2

     示例 2：
     输入：x = 8
     输出：2
     解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

     分析：
     1.二分查找,始终保证目标值在【min ，max】中
       此处防止溢出，应该用除法

     边界值 & 注意点：
     1.  0、1、2
     2.  边界值:2147483647   46341 *  46341
     **/
    //大神优化：
    public int mySqrt1(int x) {//3
        //max 最大值 = x/2+1    ，min = 0
        if(x<2) return x;
        int max = x/2 +1 ;
        int min = 0 ;
        while (min<=max){
            int midlle = min +((max-min)>>1);//防止溢出
            int shang = x/midlle;//防止溢出，改用除法，
            if(midlle > shang){//目标值值比midlle 大，在[minn,midlle-1] 区间
                max = midlle-1;
            }else if(midlle<shang){//目标值值比midlle 小  ，在[midlle+1,max] 区间
                min = midlle+1;
            }else return  midlle;
        }
        return max;
    }

    public int mySqrt(int x) {
        //注意特殊情况
        //1.  0、1、2
        //2.  边界值:2147483647   46341 *  46341  = -.....
        for (int i = 0; i <= (x)/2+1; i++) {
            if(i*i==x) return  i;
            if(i*i>x) return  i-1;
            if(i*i<0){
                return  i-1;
            }
        }
        return 1;
    }
}
